//给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以
//穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。 
//
// 给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 
//10⁹ + 7 取余 后的结果。 
//
// 
//
// 示例 1： 
// 
// 
//输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
//输出：6
// 
//
// 示例 2： 
// 
// 
//输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
//输出：12
// 
//
// 
//
// 提示： 
//
// 
// 1 <= m, n <= 50 
// 0 <= maxMove <= 50 
// 0 <= startRow < m 
// 0 <= startColumn < n 
// 
//
// Related Topics 动态规划 👍 299 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.Arrays;

public class OutOfBoundaryPaths {
    public static void main(String[] args) {
        Solution solution = new OutOfBoundaryPaths().new Solution();
        solution.findPaths(2, 2, 1, 0, 0);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int mod = (int) 1e9 + 7;
        int N;
        int MAXMOVE;

        int[][] cache;
        //上下左右
        int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        /**
         * 计划搜索
         *
         * @param m
         * @param n
         * @param maxMove
         * @param startRow
         * @param startColumn
         * @return
         */
        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
            cache = new int[m * n][maxMove + 1];
            //初始化cache 为-1区分为0的情况
            for (int i = 0; i < m * n; i++) {
                Arrays.fill(cache[i], -1);
            }
            return dfs(m, n, maxMove, startRow, startColumn);
        }

        private int dfs(int m, int n, int maxMove, int startRow, int startColumn) {
            //base case1:如果出界 就返回1
            if (startRow < 0 || startRow>=m || startColumn<0 || startColumn>=n) return 1;

            //base case2: 如果maxMove为0 并且没有出界 返回0
            if (startRow >= 0 && startRow < m && startColumn >= 0 && startColumn < n && maxMove <= 0) return 0;

            //如果cache里面有 直接返回
            if (cache[getIndex(startRow,startColumn, n)][maxMove] != -1) {
                return cache[getIndex(startRow,startColumn, n)][maxMove];
            }
            //然后可以向四周dfs
            int sum = 0;
            for (int[] d : dir) {
                sum += dfs(m,n,maxMove-1,startRow+d[0],startColumn+d[1]);
                sum%=mod;
            }
            cache[getIndex(startRow,startColumn, n)][maxMove] = sum;
            return sum;
        }

        public int getIndex(int m, int n, int col) {
            return m * col + n;
        }

        /**
         * 动态规划
         * @param m
         * @param n
         * @param maxMove
         * @param startRow
         * @param startColumn
         * @return
         */
//        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
//            int[][] dp = new int[m*n][maxMove+1];
//            N=n;
//            MAXMOVE = maxMove;
//            for (int i = 0; i < m; i++) {
//                for (int j = 0; j < n; j++) {
//                    if (i == 0) add(i,j,dp);
//                    if (i == m - 1) add(i, j, dp);
//                    if (j == 0) add(i, j, dp);
//                    if (j == n - 1) add(i, j, dp);
//                }
//            }
//            // 定义可移动的四个方向
//            int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
//
//            for (int curr = 1; curr <= maxMove; curr++) {
//                for (int k = 0; k < m * n; k++) {
//                    int x = parseIdx(k)[0];
//                    int y = parseIdx(k)[1];
//                    for (int[] d : dirs) {
//                        int nx = x + d[0];
//                        int ny = y + d[1];
//                        if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
//                            dp[k][curr] += dp[getIndex(nx, ny)][curr - 1];
//                            dp[k][curr] %= mod;
//                        }
//                    }
//
//                }
//            }
//            return dp[getIndex(startRow,startColumn)][maxMove];
//        }
//
//        // 为每个「边缘」格子，添加一条路径
//        void add(int x, int y, int[][] f) {
//            int idx = getIndex(x, y);
//            for (int step = 1; step <= MAXMOVE; step++) {
//                f[idx][step]++;
//            }
//        }
//
//        int getIndex(int x, int y) {
//            return x * N + y;
//        }
//
//        // 将 index 解析回 (x, y)
//        int[] parseIdx(int idx) {
//            return new int[]{idx / N, idx % N};
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}